package zuoye29.zuoye9;

public class chongfu {
    public static void main(String[] args) {
//        9：定义一个字符串，找出其中最长的重复字符串，比如
//        abcfabc,则结果是abc；比如 afkafk,则结果是afk.
        String input = "abcfabc";
        String longestRepeatedSubstring = findLongestRepeatedSubstring(input);
        System.out.println("Longest repeated substring: " + longestRepeatedSubstring);
    }

    public static String findLongestRepeatedSubstring(String input) {
        if (input == null || input.length() == 0) {
            return "";
        }

        char[] inputChars = input.toCharArray();
        int[][] dp = new int[inputChars.length][inputChars.length];
        int maxLength = 0;
        String longestRepeatedSubstring = "";

        for (int i = 0; i < inputChars.length; i++) {
            for (int j = i + 1; j < inputChars.length; j++) {
                if (inputChars[i] == inputChars[j]) {
                    dp[i][j] = dp[i + 1][j - 1] + 1;
                    if (dp[i][j] > maxLength) {
                        maxLength = dp[i][j];
                        longestRepeatedSubstring = input.substring(i, j + 1);
                    }
                } else {
                    dp[i][j] = 0;
                }
            }
        }

        return longestRepeatedSubstring;

    }
}
